I. Field of the Invention
The present invention relates to the field of microprocessors. More specifically, the present invention relates to branch prediction in microprocessors.
II. Background Information
Computer programs typically include a large number of branch instructions which, upon execution, may cause instructions to be executed in a sequence other than the sequence set forth in the program memory. When a branch instruction is executed, execution continues either with the next sequential instruction from memory or execution jumps to an instruction specified by a branch target address. A branch specified by the branch instruction is said to be xe2x80x9cTakenxe2x80x9d if execution jumps to the instruction specified by the branch target address and xe2x80x9cNot Takenxe2x80x9d if execution continues with the next sequential instruction from memory.
Branch instructions are either unconditional or conditional. An unconditional branch is Taken every time the instruction is executed. A conditional branch instruction is Taken or Not Taken depending upon resolution of a condition which usually is a result of a logic statement. The instructions that are to be executed following a conditional branch are not known with certainty until the condition upon which the branch depends has been resolved. However, rather than waiting until the condition is resolved, state-of-the-art microprocessors perform branch prediction whereby the microprocessor tries to guess whether the branch will be Taken or Not Taken, so the instructions following the branch may be fetched and executed speculatively. If a branch is predicted to be Not Taken, the microprocessor fetches and speculatively executes the next sequential instruction after the branch from the memory. If the branch is predicted to be Taken, the microprocessor fetches and speculatively executes the instruction at the predicted branch target address. The instructions executed following the branch prediction are xe2x80x9cspeculativexe2x80x9d because the microprocessor does not yet know whether the prediction will be correct or not. Accordingly, any operations caused to be performed by the speculative instructions may not be fully completed. For example, if a memory write operation is performed speculatively, the write operation may not be forwarded to a memory system until all previous branch conditions are executed successfully. Otherwise an instruction in a mispredicted path may improperly alter the contents of the memory.
If the branch prediction is ultimately determined to be correct, the speculatively executed instructions are retired or otherwise committed. In the example of a memory write, retirement is performed by forwarding the write operation to the memory system. If the branch prediction is ultimately found to be incorrect, then any speculatively executed instructions following the mispredicted branch are typically flushed from the system. In the memory write example, the write is not forwarded to the memory system but rather is discarded.
To expedite branch prediction, some state-of-the-art microprocessors include a branch prediction table (BPT) that provides a cache of the most recently predicted branches along with corresponding prediction information such as history of previous executions, also known as dynamic history, and/or predictions for that branch and the success thereof.
In addition to dynamic branch history, prediction mechanisms may also utilize compiler hints to aide the branch prediction. Usually, the compiler hints are determined using program profiling which is acquired by running a program with several sample data sets. From profiling a compiler, one may know whether or not a branch is likely to be taken and how certain the branch is taken or not taken. This information may be encoded into an instruction. However, to find out this information from the instruction, the instruction needs to be read from the instruction cache and decoded. The problem is that an instruction is decoded later in the pipeline. Therefore, the information encoded in the instruction is not available until several stages down the pipeline.
One embodiment of the present invention includes a microprocessor. The microprocessor includes a branch prediction table (BPT) that has at least one branch entry. The at least one branch entry includes a prediction field to indicate whether a branch is predicted taken. The at least one branch entry also includes a history register to store history information. Moreover, the BPT includes a prediction update logic to update the prediction field and the history register except when a branch is strongly predicted statically.